相信昨天的第一題應該是沒有辦法滿足大家的對吧(相信在座的各位都是大神)
那今天我們就來講講第二題:Add Two Numbers

題目:

講解:

有兩個以鏈結串列表示的非負整數，數字的位數是逆序存放的（位數較小的數字在前面）。每個鏈結串列的節點代表數字的一位。我們需要將這兩個鏈結串列所代表的數字相加，並將結果以同樣的鏈結串列形式回傳。

解題思路:

這道題目要求將兩個以鏈結串列表示的非負整數相加，數字的每一位是逆序存放的（即最小位數存儲在鏈結串列的頭部）。我們需要從鏈結串列的頭開始逐位相加，並考慮進位，最終返回一個同樣逆序存放結果的鏈結串列。

例如，l1 = [2 -> 4 -> 3] 和 l2 = [5 -> 6 -> 4] 表示數字 342 和 465。相加的結果是 807，對應的鏈結串列應為 [7 -> 0 -> 8]。

步驟

1.初始化：

• 創建一個虛擬頭節點 l3，這樣我們可以簡化結果鏈結串列的處理過程，同時設置指標 r 指向 l3，用來構建最終結果的鏈結串列。
• 初始化進位變量 carry，用來處理每次相加的進位，初始值設為 0。

2.迴圈處理每一位數字：

• 使用一個 while 迴圈，在 l1、l2 或 carry 有任意一個不為零的情況下繼續執行。
• 每次進行加法運算時，從 carry 開始加，然後依次加上 l1 和 l2 的對應節點值（如果節點存在）。
• 更新進位 carry，將總和除以 10，這樣進位的數字就會儲存在 carry 中。
• 新增一個新節點來保存當前的數字（即總和對 10 取餘數），並將其連接到結果鏈結串列中。

3.處理剩餘的進位：

• 如果鏈結串列遍歷完成後還有進位（carry != 0），需要在結果鏈結串列中再加一個新節點來存儲進位。

4.返回結果：

• 最後結果鏈結串列的頭節點是虛擬節點 l3 的下一個節點，因此返回 l3->next 即可。

code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l3 = new ListNode(0);  // 虛擬頭節點
        ListNode* r = l3;                // 指向結果鏈結串列的指標
        int carry = 0;                   // 進位變量

        // 當 l1、l2 或 carry 不為零時繼續迴圈
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;  // 每次都從進位開始計算
            if (l1 != nullptr) {  // 如果 l1 還有節點
                sum += l1->val;
                l1 = l1->next;    // 移動到下一個節點
            }
            if (l2 != nullptr) {  // 如果 l2 還有節點
                sum += l2->val;
                l2 = l2->next;    // 移動到下一個節點
            }
            carry = sum / 10;    // 計算新的進位
            r->next = new ListNode(sum % 10);  // 添加新節點保存當前位數的值
            r = r->next;         // 移動到結果鏈結串列的下一個節點
        }

        return l3->next;  // 返回結果鏈結串列的起始節點
    }
};